package Z.dailyExercise.May;

import java.util.ArrayList;
import java.util.List;

public class _15三数之和 {
    public static void main(String[] args) {
        _15三数之和 test = new _15三数之和();
        test.threeSum(new int[]{-1,0,1,2,-1,-4});
    }

    /**
     * 回溯法--会超时。。。
     * @param nums
     * @return
     */
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> choice = new ArrayList<>();
    int addnum = 0;
    public List<List<Integer>> threeSum(int[] nums) {
        backtrace(nums,0);
        return res;


    }

    public void backtrace(int[] nums,int index){

        if (  choice.size()== 3 && addnum==0){
            if (res.contains(choice)){
                return;
            }
            res.add(new ArrayList<>(choice));
            return;
        }
        if (choice.size()> 3){
            return;
        }

        for (int i = index; i < nums.length; i++) {
            addnum += nums[i];
            choice.add(nums[i]);
            backtrace(nums,index+1);

            int out = choice.get(choice.size()-1);
            choice.remove(choice.size()-1);
            addnum -= out;


        }
    }

}
